home *** CD-ROM | disk | FTP | other *** search
/ Mac Power 1997 December / MACPOWER-1997-12.ISO.7z / MACPOWER-1997-12.ISO / AMUG / PROGRAMMING / Raven 1.2.sit / Raven 1.2 / • Extras • / SGI STL / deque.h < prev    next >
C/C++ Source or Header  |  1997-05-28  |  31KB  |  973 lines
  1. /*
  2.  *
  3.  * Copyright (c) 1994
  4.  * Hewlett-Packard Company
  5.  *
  6.  * Permission to use, copy, modify, distribute and sell this software
  7.  * and its documentation for any purpose is hereby granted without fee,
  8.  * provided that the above copyright notice appear in all copies and
  9.  * that both that copyright notice and this permission notice appear
  10.  * in supporting documentation.  Hewlett-Packard Company makes no
  11.  * representations about the suitability of this software for any
  12.  * purpose.  It is provided "as is" without express or implied warranty.
  13.  *
  14.  *
  15.  * Copyright (c) 1996
  16.  * Silicon Graphics Computer Systems, Inc.
  17.  *
  18.  * Permission to use, copy, modify, distribute and sell this software
  19.  * and its documentation for any purpose is hereby granted without fee,
  20.  * provided that the above copyright notice appear in all copies and
  21.  * that both that copyright notice and this permission notice appear
  22.  * in supporting documentation.  Silicon Graphics makes no
  23.  * representations about the suitability of this software for any
  24.  * purpose.  It is provided "as is" without express or implied warranty.
  25.  *
  26.  * Exception Handling:
  27.  * Copyright (c) 1997
  28.  * Mark of the Unicorn, Inc.
  29.  *
  30.  * Permission to use, copy, modify, distribute and sell this software
  31.  * and its documentation for any purpose is hereby granted without fee,
  32.  * provided that the above copyright notice appear in all copies and
  33.  * that both that copyright notice and this permission notice appear
  34.  * in supporting documentation.  Mark of the Unicorn makes no
  35.  * representations about the suitability of this software for any
  36.  * purpose.  It is provided "as is" without express or implied warranty.
  37.  *
  38.  * Adaptation:
  39.  * Copyright (c) 1997
  40.  * Moscow Center for SPARC Technology
  41.  *
  42.  * Permission to use, copy, modify, distribute and sell this software
  43.  * and its documentation for any purpose is hereby granted without fee,
  44.  * provided that the above copyright notice appear in all copies and
  45.  * that both that copyright notice and this permission notice appear
  46.  * in supporting documentation.  Moscow Center for SPARC Technology makes no
  47.  * representations about the suitability of this software for any
  48.  * purpose.  It is provided "as is" without express or implied warranty.
  49.  *
  50.  */
  51.  
  52. #ifndef __SGI_STL_DEQUE_H
  53. #define __SGI_STL_DEQUE_H
  54.  
  55. #include <stddef.h>
  56. # ifndef __SGI_STL_ALGOBASE_H
  57. #  include <algobase.h>
  58. # endif
  59. # ifndef __SGI_STL_ALLOC_H
  60. #include <alloc.h>
  61. # endif
  62.  
  63. # if defined ( __STL_USE_ABBREVS )
  64. #  define __deque_iterator         _dQ__It
  65. #  define __deque_const_iterator   _dQ__cIt
  66. # endif
  67.  
  68. __BEGIN_STL_NAMESPACE
  69.  
  70. inline size_t __deque_buf_size(size_t sz)
  71. {
  72.   return sz < 4096 ? size_t(4096 / sz) : size_t(1);
  73. }
  74.  
  75. template <class T> struct __deque_iterator;
  76. template <class T> struct __deque_const_iterator;
  77. template <class T> struct __deque_data;
  78.  
  79. template <class T>
  80. struct __deque_iterator_base 
  81. # if defined ( __STL_DEBUG )
  82.     : public __safe_base 
  83. # endif
  84. {
  85. private:
  86.   typedef __deque_iterator_base<T> self;
  87. public:
  88.   typedef T value_type;
  89.   typedef value_type* pointer;
  90.   typedef value_type& reference;
  91.   typedef const value_type& const_reference;
  92.   typedef size_t size_type;
  93.   typedef ptrdiff_t difference_type;
  94.   typedef pointer* map_pointer;
  95.  
  96.   pointer current;
  97.   pointer first;
  98.   pointer last;
  99.   map_pointer node;
  100.  
  101.   static size_type buffer_size() {
  102.     return __deque_buf_size(sizeof(value_type)); }
  103.     void construct(pointer x, map_pointer y) {
  104.         current=x; first=*y; last=(*y + buffer_size()); node=y;
  105.     }
  106.     void construct() {
  107.         current=0; first=0; last=0; node=0;
  108.     }
  109.     void construct(const self& x) {
  110.         current=x.current; first=x.first; last=x.last; node=x.node;
  111.     }
  112. # if defined ( __STL_DEBUG )
  113.   typedef const __deque_data<T>* base_ptr; 
  114.   const self& get_iterator() const { return *this; }  
  115.   const base_ptr owner() const {
  116.       return base_ptr(__safe_base::owner());
  117.   }
  118.   __deque_iterator_base(const __safe_base* root, pointer x, map_pointer y) 
  119.     : __safe_base(root) { construct(x,y);}
  120.   __deque_iterator_base() : __safe_base(0), current(0), first(0), last(0), node(0) {}
  121. # else
  122.   __deque_iterator_base(pointer x, map_pointer y) 
  123.     { construct(x,y);}
  124.   __deque_iterator_base() : current(0), first(0), last(0), node(0) {}
  125. # endif
  126.   difference_type operator-(const self& x) const {
  127.     return node == x.node 
  128.       ? current - x.current 
  129.       : difference_type(buffer_size() * (node - x.node - 1) +
  130.                         (current - first) + (x.last - x.current));
  131.   }
  132.   void operator++() {
  133.     __stl_debug_check(__check_advance(*this,1));    
  134.     if (++current == last) {
  135.       first = *(++node);
  136.       current = first;
  137.       last = first + buffer_size();
  138.     }
  139.   }
  140.   void operator--() {
  141.     __stl_debug_check(__check_advance(*this,-1));    
  142.     if (current == first) {
  143.       first = *(--node);
  144.       last = first + buffer_size();
  145.       current = last;
  146.     }
  147.     --current;
  148.   }
  149.   void operator+=(difference_type n) {
  150.     __stl_debug_check(__check_advance(*this,n));    
  151.     difference_type offset = n + (current - first);
  152.     difference_type num_node_to_jump = offset >= 0
  153.       ? offset / buffer_size()
  154.       : -((-offset + (difference_type)buffer_size() - 1) / (difference_type)buffer_size());
  155.     if (num_node_to_jump == 0)
  156.       current += n;
  157.     else {
  158.       node = node + num_node_to_jump;
  159.       first = *node;
  160.       last = first + buffer_size();
  161.       current = first + (offset - num_node_to_jump * buffer_size());
  162.     }
  163.   }
  164.  
  165.   bool operator==(const self& x) const {      
  166.      __stl_debug_check(__check_same_owner(*this,x));    
  167.      return current == x.current || 
  168.       ((current == first || x.current == x.first) && 
  169.        *this - x == 0);
  170.   }
  171.   bool operator!=(const self& x) const {return !(*this == x); }
  172.   bool operator<(const self& x) const {
  173.       __stl_debug_check(__check_same_owner(*this,x));    
  174.       return (node == x.node) ? (current < x.current) : (node < x.node);
  175.   }
  176. };
  177.  
  178. template <class T>
  179. struct __deque_iterator : public __deque_iterator_base<T> {
  180. private:
  181.   typedef __deque_iterator_base<T> super;
  182. public:
  183.   typedef __deque_iterator<T> iterator;
  184.   typedef __deque_const_iterator<T> const_iterator;
  185.   __deque_iterator() {}
  186. # if defined ( __STL_DEBUG )
  187.     __deque_iterator(const __safe_base* root, pointer x, map_pointer y) : 
  188.         super(root,x,y) {}
  189. # else
  190.     __deque_iterator(pointer x, map_pointer y) : super(x,y) {}
  191. # endif
  192.   reference operator*() const { 
  193.           __stl_debug_check(__check_dereferenceable(*this));    
  194.           return *current; 
  195.   }
  196.   difference_type operator-(const iterator& x) const {
  197.       return super::operator-(x);
  198.   }
  199.   iterator& operator++() {
  200.     super::operator++();
  201.     return *this; 
  202.   }
  203.   iterator operator++(int)  {
  204.     iterator tmp = *this;
  205.     ++*this;
  206.     return tmp;
  207.   }
  208.   iterator& operator--() {
  209.     super::operator--();
  210.     return *this;
  211.   }
  212.   iterator operator--(int) {
  213.     iterator tmp = *this;
  214.     --*this;
  215.     return tmp;
  216.   }
  217.   iterator& operator+=(difference_type n) {
  218.     super::operator+=(n);
  219.     return *this;
  220.   }
  221.   iterator& operator-=(difference_type n) { return *this += -n; }
  222.   iterator operator+(difference_type n) const {
  223.     iterator tmp = *this;
  224.     return tmp += n;
  225.   }
  226.   iterator operator-(difference_type n) const {
  227.     iterator tmp = *this;
  228.     return tmp -= n;
  229.   }
  230.   reference operator[](difference_type n) const { return *(*this + n); }
  231.   bool operator==(const iterator& x) const {      
  232.       return super::operator==(x);
  233.   }
  234.   bool operator!=(const iterator& x) const { return !(*this == x); }
  235.   bool operator<(const iterator& x) const {
  236.      return super::operator<(x);
  237.   }
  238. };
  239.  
  240.  
  241. template <class T>
  242. struct __deque_const_iterator : public __deque_iterator_base<T> {
  243. private:
  244.     typedef __deque_iterator_base<T> super;
  245. public:
  246.   typedef __deque_iterator<T> iterator;
  247.   typedef __deque_const_iterator<T> const_iterator;
  248.   __deque_const_iterator() {}
  249. # if defined ( __STL_DEBUG )
  250.     __deque_const_iterator(const __safe_base* root, pointer x, map_pointer y) : 
  251.         super(root,x,y) {}
  252.     __deque_const_iterator(const iterator& x) : 
  253.         super(x) {}     
  254. # else
  255.     __deque_const_iterator(pointer x, map_pointer y) : super(x,y) {}
  256.     __deque_const_iterator(const iterator& x) : 
  257.         super(x) {}     
  258. # endif
  259.   const_reference operator*() const { 
  260.     return *current;
  261.   }
  262.   difference_type operator-(const const_iterator& x) const {
  263.       return super::operator-(x);
  264.   }
  265.   const_iterator& operator++() {
  266.     super::operator++();
  267.     return *this; 
  268.   }
  269.   const_iterator operator++(int)  {
  270.     const_iterator tmp = *this;
  271.     ++*this;
  272.     return tmp;
  273.   }
  274.   const_iterator& operator--() {
  275.     super::operator--();
  276.     return *this;
  277.   }
  278.   const_iterator operator--(int) {
  279.     const_iterator tmp = *this;
  280.     --*this;
  281.     return tmp;
  282.   }
  283.   const_iterator& operator+=(difference_type n) {
  284.     super::operator+=(n);
  285.     return *this;
  286.   }
  287.   const_iterator& operator-=(difference_type n) { return *this += -n; }
  288.   const_iterator operator+(difference_type n) const {
  289.     const_iterator tmp = *this;
  290.     return tmp += n;
  291.   }
  292.   const_iterator operator-(difference_type n) const {
  293.     const_iterator tmp = *this;
  294.     return tmp -= n;
  295.   }
  296.   const_reference operator[](difference_type n) const { return *(*this + n); }
  297.   bool operator==(const const_iterator& x) const {      
  298.       return super::operator==(x);
  299.   }
  300.   bool operator!=(const const_iterator& x) const {return !(*this == x); }
  301.   bool operator<(const const_iterator& x) const {
  302.       return super::operator<(x);
  303.   }
  304. };
  305.  
  306.  
  307. template <class T>
  308. inline random_access_iterator_tag
  309. iterator_category(const __deque_iterator<T>&) {
  310.   return random_access_iterator_tag();
  311. }
  312.  
  313. template <class T>
  314. inline T*
  315. value_type(const __deque_iterator<T>&) {
  316.   return (T*) 0;
  317. }
  318.  
  319. template <class T>
  320. inline ptrdiff_t*
  321. distance_type(const __deque_iterator<T>&) {
  322.   return (ptrdiff_t*) 0;
  323. }
  324.  
  325. template <class T>
  326. inline random_access_iterator_tag
  327. iterator_category(const __deque_const_iterator<T>&) {
  328.   return random_access_iterator_tag();
  329. }
  330.  
  331. template <class T>
  332. inline T*
  333. value_type(const __deque_const_iterator<T>&) {
  334.   return (T*) 0;
  335. }
  336.  
  337. template <class T>
  338. inline ptrdiff_t*
  339. distance_type(const __deque_const_iterator<T>&) {
  340.   return (ptrdiff_t*) 0;
  341. }
  342.  
  343. template <class T>
  344. struct __deque_data 
  345. # if defined ( __STL_DEBUG )
  346.     : public __safe_base 
  347. # endif
  348. {
  349.     typedef T value_type;
  350.     typedef size_t size_type;
  351.     typedef ptrdiff_t difference_type;
  352.     typedef T** map_pointer;
  353. protected:
  354.     __deque_iterator<T> start;
  355.     __deque_iterator<T> finish;
  356.     size_type length;
  357.     map_pointer map;
  358.     size_type map_size;
  359. public:
  360.     __deque_data() : start(), finish(), length(0), map(0), map_size(0) {
  361.             __stl_debug_do(safe_init(this));
  362.             __stl_debug_do(start.safe_init(this));
  363.             __stl_debug_do(finish.safe_init(this));
  364.     }
  365.     ~__deque_data() {
  366.         __stl_debug_do(invalidate()); __stl_debug_do(start.invalidate()); 
  367.         __stl_debug_do(finish.invalidate());
  368.     }
  369. # if defined (__STL_DEBUG)
  370. public:
  371.     inline bool dereferenceable(const __deque_iterator_base<T>& it) const {
  372.         return (it!=finish);
  373.     }
  374.     inline bool valid_advance(const __deque_iterator_base<T>& it, difference_type n) const {
  375.         difference_type new_pos((it-start)+n);
  376.         return  (new_pos>=0 && new_pos <= (difference_type)length);
  377.     }
  378.     void invalidate_iterator(const __deque_iterator_base<T>& it) { 
  379.         __invalidate_iterator(this,it,it);
  380.     }
  381. # endif
  382. };
  383.  
  384. template <class T, class Alloc>
  385. class __deque_base : public __deque_data <T> {
  386.     typedef __deque_base<T,Alloc> self;
  387.     typedef T value_type;
  388.     typedef value_type* pointer;
  389.     typedef size_t size_type;
  390.     typedef Alloc allocator_type;
  391. protected:
  392.     static size_type buffer_size() {
  393.         return __deque_buf_size(sizeof(value_type)); }
  394.     static size_type init_map_size() {
  395.         return __deque_buf_size(sizeof(pointer)); }
  396.     void deallocate_at_begin();
  397. public:
  398.     typedef simple_alloc<value_type*, allocator_type> map_allocator;
  399.     typedef simple_alloc<value_type, allocator_type> data_allocator;
  400.     __deque_base() {}
  401.     ~__deque_base() { clear(); }
  402.     void pop_front() {
  403.         destroy(start.current);
  404.         ++start.current;
  405.         --length;
  406.         if ((length == 0) || start.current == start.last)
  407.             deallocate_at_begin();
  408.     }
  409.     void clear() { while (length!=0) pop_front(); }
  410. };
  411.  
  412. template <class T , class Alloc>
  413. void __deque_base<T, Alloc>::deallocate_at_begin() {
  414.     data_allocator::deallocate(*start.node++, buffer_size());
  415.     if (length==0) {
  416.         if (finish.current == finish.first) 
  417.             data_allocator::deallocate(*start.node, buffer_size());
  418.         start.construct();
  419.         finish.construct();
  420.         map_allocator::deallocate(map, map_size);
  421.     } else
  422.         start.construct(*start.node, start.node);
  423. }
  424.  
  425.  
  426. __BEGIN_STL_FULL_NAMESPACE
  427. #  define deque __WORKAROUND_RENAME(deque)
  428.  
  429. template <class T, __DFL_TYPE_PARAM(Alloc,alloc) >
  430. class deque : public __deque_base<T,Alloc> {
  431.     typedef __deque_base<T, Alloc> super;
  432.     typedef deque<T, Alloc> self;
  433. public:
  434.     typedef T value_type;
  435.     typedef size_t size_type;
  436.     typedef value_type* pointer;
  437.     typedef const value_type* const_pointer;
  438.     typedef value_type& reference;
  439.     typedef const value_type& const_reference;
  440.     typedef ptrdiff_t difference_type;
  441.     typedef __deque_iterator<T> iterator;
  442.     typedef __deque_const_iterator<T> const_iterator;
  443.     typedef reverse_iterator<const_iterator, value_type, const_reference, 
  444.     difference_type>  const_reverse_iterator;
  445.     typedef reverse_iterator<iterator, value_type, reference, difference_type>
  446.     reverse_iterator; 
  447. protected:    
  448.     typedef pointer* map_pointer;
  449.     void allocate_at_begin();
  450.     void allocate_at_end();
  451.     void deallocate_at_end();
  452. public:
  453.     deque() { }
  454.     iterator begin() { return start; }
  455.     const_iterator begin() const { return start; }
  456.     iterator end() { return finish; }
  457.     const_iterator end() const { return finish; }
  458.     reverse_iterator rbegin() { return reverse_iterator(end()); }
  459.     const_reverse_iterator rbegin() const { 
  460.         return const_reverse_iterator(end()); 
  461.     }
  462.     reverse_iterator rend() { return reverse_iterator(begin()); }
  463.     const_reverse_iterator rend() const { 
  464.         return const_reverse_iterator(begin()); 
  465.     }
  466.     bool empty() const { return length == 0; }
  467.     size_type size() const { return length; }
  468.     size_type max_size() const { return size_type(-1); }
  469.     reference operator[](size_type n) { return *(begin() + n); }
  470.     const_reference operator[](size_type n) const { return *(begin() + n); }
  471.     reference front() { return *begin(); }
  472.     const_reference front() const { return *begin(); }
  473.     reference back() { return *(end() - 1); }
  474.     const_reference back() const { return *(end() - 1); }
  475. private:
  476.  
  477. #  if defined (__STL_USE_EXCEPTIONS) 
  478.     void push_back_cleanup(int steps_remaining);
  479.     void push_front_cleanup(int steps_remaining, bool allocated_at_begin);
  480.     class push_back_protector;
  481.     friend class push_back_protector;
  482.     class push_back_protector
  483.     {
  484.         typedef deque<T,Alloc> deque_type;
  485.         deque_type *container;
  486.         int steps_remaining;
  487.     public:
  488.         push_back_protector(deque_type* d) : container(d), steps_remaining(2) {}
  489.         ~push_back_protector() { 
  490.             if (steps_remaining) 
  491.                 container->push_back_cleanup(steps_remaining); 
  492.         }
  493.         void constructed() { steps_remaining = 1; }
  494.         void done() { steps_remaining = 0; }
  495.     };
  496.     
  497.     class push_front_protector;
  498.     friend class push_front_protector;
  499.     class push_front_protector
  500.     {
  501.         typedef deque<T,Alloc> deque_type;
  502.         deque_type *container;
  503.         int steps_remaining;
  504.         bool allocated_at_begin;
  505.     public:
  506.         push_front_protector(deque_type* d, bool alloc_at_begin)
  507.             : container(d), steps_remaining(2), allocated_at_begin(alloc_at_begin) {}
  508.         ~push_front_protector() {
  509.             if (steps_remaining )
  510.                 container->push_front_cleanup(steps_remaining, allocated_at_begin);
  511.         }
  512.         void constructed() { steps_remaining = 1; }
  513.         void done() { steps_remaining = 0; }
  514.     };
  515. #  else    
  516.     class push_front_protector;
  517.     class push_front_protector
  518.     {
  519.     public:
  520.         push_front_protector(void*, bool=bool()){}
  521.         ~push_front_protector() {}
  522.         void constructed() {}
  523.         void done() {}
  524.     };
  525.     typedef push_front_protector push_back_protector;
  526. #  endif
  527.  
  528. public:
  529.     void push_back(const T& x) {
  530.         if (empty()) allocate_at_end();
  531.         push_back_protector protector(this);
  532.         construct(finish.current, x);
  533.         protector.constructed();
  534.         ++finish.current;
  535.         ++length;
  536.         if (finish.current == finish.last) allocate_at_end();
  537.         protector.done();
  538.         __stl_debug_do(invalidate_all());
  539.     }
  540.     void push_front(const T& x) {
  541.         bool alloc_at_begin = empty() || start.current == start.first;
  542.         if (alloc_at_begin) allocate_at_begin();
  543.         push_front_protector protector(this, alloc_at_begin);
  544.         --start.current;
  545.         construct(start.current, x);
  546.         protector.constructed();
  547.         ++length;
  548.         if (finish.current == finish.last) allocate_at_end();
  549.         protector.done();
  550.         __stl_debug_do(invalidate_all());
  551.     }
  552.     void pop_front() {
  553.         __stl_debug_do(invalidate_iterator(start));        
  554.         super::pop_front();
  555.     }
  556.     void pop_back() {
  557.         __stl_debug_do(invalidate_iterator(finish));
  558.         if (finish.current == finish.first) deallocate_at_end();
  559.         --finish.current;
  560.         destroy(finish.current);
  561.         --length; 
  562.         if (empty()) deallocate_at_end();
  563.     }
  564.     void swap(deque<T, Alloc>& x) {
  565.         __STL_NAMESPACE::swap(start, x.start);
  566.         __STL_NAMESPACE::swap(finish, x.finish);
  567.         __STL_NAMESPACE::swap(length, x.length);
  568.         __STL_NAMESPACE::swap(map, x.map);
  569.         __STL_NAMESPACE::swap(map_size, x.map_size);
  570.         __stl_debug_do(swap_owners(x));
  571.     }
  572.     iterator insert(iterator position, const T& x);
  573.     iterator insert(iterator position) { return insert(position, T()); }
  574.     void insert(iterator position, size_type n, const T& x);
  575. //  template <class Iterator> void insert(iterator position,
  576. //                                        Iterator first, Iterator last);
  577.     void insert(iterator position, const T* first, const T* last);
  578.     void insert(iterator position, const_iterator first, const_iterator last);
  579.     void erase(iterator position);
  580.     void erase(iterator first, iterator last);    
  581.     void resize(size_type new_size, const T& x) {
  582.         if (new_size < size()) 
  583.             erase(begin() + new_size, end());
  584.         else
  585.             insert(end(), new_size - size(), x);
  586.     }
  587.     void resize(size_type new_size) { resize(new_size, T()); }
  588. public:
  589.     deque(size_type n, const T& value) {
  590.         insert(begin(), n, value);
  591.     }
  592.     explicit deque(size_type n) {
  593.         insert(begin(), n, T());
  594.     }
  595. //  template <class Iterator> deque(Iterator first, Iterator last);
  596.     deque(const T* first, const T* last) {
  597.         copy(first, last, back_inserter(*this));
  598.     }
  599.     deque(const_iterator first, const_iterator last) {
  600.         copy(first, last, back_inserter(*this));
  601.     }
  602.     deque(const self& x)  {
  603.         copy(x.begin(), x.end(), back_inserter(*this));
  604.     }
  605.     self& operator=(const self& x) {
  606.         if (this != &x) {
  607.             if (size() >= x.size()) 
  608.                 erase(copy(x.begin(), x.end(), begin()), end());
  609.             else 
  610.                 copy(x.begin() + size(), x.end(),
  611.                      inserter(*this, copy(x.begin(), x.begin() + size(),
  612.                                           begin())));
  613.             __stl_debug_do(invalidate_all());
  614.         }
  615.         return *this;
  616.     }
  617.     ~deque() {}
  618. };
  619.  
  620. # if defined ( __STL_NESTED_TYPE_PARAM_BUG )
  621. // qualified references 
  622. #   define __iterator__           __deque_iterator<T>
  623. #   define iterator               __iterator__
  624. #   define const_iterator         __deque_const_iterator<T> 
  625. #  define size_type              size_t
  626. # else
  627. #  define __iterator__           deque<T,Alloc>::iterator
  628. # endif
  629.  
  630. #  if defined (__STL_USE_EXCEPTIONS) 
  631. template <class T , class Alloc>
  632. inline void 
  633. deque<T, Alloc>::push_front_cleanup(int steps_remaining, bool allocated_at_begin)
  634. {
  635.     if (steps_remaining == 1) {    // construct succeeded?
  636.         destroy(start.current);
  637.         --length; 
  638.     }
  639.     ++start.current;
  640.     if (allocated_at_begin)
  641.         deallocate_at_begin();
  642. }
  643.  
  644. template <class T , class Alloc>
  645. inline void 
  646. deque<T, Alloc>::push_back_cleanup(int steps_remaining)
  647. {
  648.     if (steps_remaining == 1) {
  649.         destroy(finish.current - 1);
  650.         --length;
  651.     }
  652.     if (empty()) deallocate_at_end();
  653. }
  654.  
  655. #  endif
  656.  
  657. template <class T , class Alloc>
  658. void deque<T, Alloc>::allocate_at_begin() {
  659. //    typedef typename self::map_allocator map_allocator;
  660.     pointer p = data_allocator::allocate(buffer_size());
  661.     __TRY {
  662.         if (!empty()) {
  663.             if (start.node == map) {
  664.                 difference_type i = finish.node - start.node;
  665.                 size_type old_map_size = map_size;
  666.                 map_pointer tmp = map_allocator::allocate((i+1)*2);
  667.                 map_size = (i+1)*2;
  668.                 // need not worry on pointers copy
  669.                 copy(start.node, finish.node + 1, tmp + map_size / 4 + 1);
  670.                 map = tmp;
  671.                 map_allocator::deallocate(map, old_map_size);
  672.                 map[map_size / 4] = p;
  673.                 start.construct(p + buffer_size(), map + map_size / 4);
  674.                 finish.construct(finish.current, map + map_size / 4 + i + 1);
  675.             } else {
  676.                 *--start.node = p;
  677.                 start.construct(p + buffer_size(), start.node);
  678.             }
  679.         } else {
  680.             size_type new_map_size = init_map_size();
  681.             map = map_allocator::allocate(new_map_size);
  682.             map_size = new_map_size;
  683.             map[map_size / 2] = p;
  684.             start.construct(p + buffer_size() / 2 + 1, map + map_size / 2);
  685.             finish.construct(start);
  686.         }
  687.     }
  688. #  if defined (__STL_USE_EXCEPTIONS) 
  689.     catch(...) {
  690.         data_allocator::deallocate(p, buffer_size());
  691.         throw;
  692.     }
  693. #endif
  694. }
  695.  
  696. template <class T , class Alloc>
  697. void deque<T, Alloc>::allocate_at_end() {
  698. //    typedef typename self::map_allocator map_allocator;
  699.     pointer p = data_allocator::allocate(buffer_size());
  700.     __TRY {
  701.         if (!empty()) {
  702.             if (finish.node == map + map_size - 1) {
  703.                 difference_type i = finish.node - start.node;
  704.                 size_type old_map_size = map_size;
  705.                 map_pointer tmp = map_allocator::allocate((i + 1) * 2);
  706.                 map_size = (i + 1) * 2;
  707.                 copy(start.node, finish.node + 1, tmp + map_size / 4);
  708.                 map_allocator::deallocate(map, old_map_size);
  709.                 map = tmp;
  710.                 map[map_size / 4 + i + 1] = p;
  711.                 start.construct(start.current, map + map_size / 4);
  712.                 finish.construct(p, map + map_size / 4 + i + 1);
  713.             } else {
  714.                 *++finish.node = p;
  715.                 finish.construct(p, finish.node);
  716.             }
  717.         } else {
  718.             size_type new_map_size = init_map_size();
  719.             map = map_allocator::allocate(new_map_size);
  720.             map_size = new_map_size;
  721.             map[map_size / 2] = p;
  722.             start.construct(p + buffer_size() / 2, map + map_size / 2);
  723.             finish.construct(start);
  724.         }
  725.     }
  726. #  if defined (__STL_USE_EXCEPTIONS) 
  727.     catch(...) {
  728.         data_allocator::deallocate(p, buffer_size());
  729.         throw;
  730.     }
  731. #  endif
  732. }
  733.  
  734. template <class T , class Alloc>
  735. void deque<T, Alloc>::deallocate_at_end() {
  736.     data_allocator::deallocate(*finish.node--, buffer_size());
  737.     if (empty()) {
  738.         start.construct();
  739.         finish.construct();
  740.         map_allocator::deallocate(map, map_size);
  741.     } else
  742.         finish.construct(*finish.node + buffer_size(), finish.node);
  743. }
  744.  
  745. template <class T , class Alloc>
  746. __iterator__ 
  747. deque<T, Alloc>::insert(iterator position, const T& x) {
  748.     __stl_verbose_assert(position.owner()==this,__STL_MSG_NOT_OWNER);    
  749.     if (position == begin()) {
  750.         push_front(x);
  751.         return begin();
  752.     } else if (position == end()) {
  753.         push_back(x);
  754.         return end() - 1;
  755.     } else {
  756.     difference_type index = position - begin();
  757.     if ((size_type)index < length / 2) {
  758.         push_front(*begin());
  759.         copy(begin() + 2, begin() + index + 1, begin() + 1); 
  760.     } else {
  761.         push_back(*(end() - 1));
  762.         copy_backward(begin() + index, end() - 2, end() - 1); 
  763.         }
  764.         *(begin() + index) = x;
  765.         return begin() + index;
  766.     }
  767. }
  768.  
  769. template <class T , class Alloc>
  770. void deque<T, Alloc>::insert(iterator position, size_type n, const T& x) {
  771.     __stl_verbose_assert(position.owner()==this,__STL_MSG_NOT_OWNER);    
  772.     difference_type index = position - begin();
  773.     difference_type remainder = length - index;
  774.     if (remainder > index) {
  775.     if (n > (size_type)index) {
  776.         difference_type m = n - index;
  777.         while (m-- > 0) push_front(x);
  778.         difference_type i = index;
  779.         while (i--) push_front(*(begin() + n - 1));
  780.         fill(begin() + n, begin() + n + index, x);
  781.     } else {
  782.         difference_type i = n;
  783.         while (i--) push_front(*(begin() + n - 1));
  784.         copy(begin() + n + n, begin() + n + index, begin() + n);
  785.         fill(begin() + index, begin() + n + index, x);
  786.     }
  787.     } else {
  788.     difference_type orig_len = index + remainder;
  789.     if (n > (size_type)remainder) {
  790.         difference_type m = n - remainder;
  791.         while (m-- > 0) push_back(x);
  792.         difference_type i = 0;
  793.         while (i < remainder) push_back(*(begin() + index + i++));
  794.         fill(begin() + index, begin() + orig_len, x);
  795.     } else {
  796.         difference_type i = 0;
  797.         while ((size_type)i < n) push_back(*(begin() + orig_len - n + i++));
  798.         copy_backward(begin() + index, begin() + orig_len - n, 
  799.               begin() + orig_len);
  800.         fill(begin() + index, begin() + index + n, x);
  801.     }
  802.     }
  803. }
  804.  
  805. template <class T , class Alloc>
  806. void deque<T, Alloc>::insert(iterator position, const T* first, const T* last) {
  807.     __stl_verbose_assert(position.owner()==this,__STL_MSG_NOT_OWNER);    
  808.     __stl_debug_check(__check_range(first,last));    
  809.     difference_type index = position - begin();
  810.     difference_type remainder = length - index;
  811.     size_type n = 0;
  812.     distance(first, last, n);
  813.     if (remainder > index) {
  814.     if (n > (size_type)index) {
  815.         const T* m = last - index;
  816.         while (m != first) push_front(*--m);
  817.         difference_type i = index;
  818.         while (i--) push_front(*(begin() + n - 1));
  819.         copy(last - index, last, begin() + n);
  820.     } else {
  821.         difference_type i = n;
  822.         while (i--) push_front(*(begin() + n - 1));
  823.         copy(begin() + n + n, begin() + n + index, begin() + n);
  824.         copy(first, last, begin() + index);
  825.     }
  826.     } else {
  827.     difference_type orig_len = index + remainder;
  828.     if (n > (size_type)remainder) {
  829.         const T* m = first + remainder;
  830.         while (m != last) push_back(*m++);
  831.         difference_type i = 0;
  832.         while (i < remainder) push_back(*(begin() + index + i++));
  833.         copy(first, first + remainder, begin() + index);
  834.     } else {
  835.         difference_type i = 0;
  836.         while ((size_type)i < n) push_back(*(begin() + orig_len - n + i++));
  837.         copy_backward(begin() + index, begin() + orig_len - n, 
  838.               begin() + orig_len);
  839.         copy(first, last, begin() + index);
  840.     }
  841.     }
  842. }
  843.  
  844. template <class T , class Alloc>
  845. void deque<T, Alloc>::insert(iterator position, const_iterator first, const_iterator last) {
  846.     __stl_verbose_assert(position.owner()==this,__STL_MSG_NOT_OWNER);    
  847.     __stl_debug_check(__check_range(first,last));    
  848.     difference_type index = position - begin();
  849.     difference_type remainder = length - index;
  850.     size_type n = 0;
  851.     distance(first, last, n);
  852.     if (remainder > index) {
  853.     if (n > (size_type)index) {
  854.         const_iterator m = last - index;
  855.         while (m != first) push_front(*--m);
  856.         difference_type i = index;
  857.         while (i--) push_front(*(begin() + n - 1));
  858.         copy(last - index, last, begin() + n);
  859.     } else {
  860.         difference_type i = n;
  861.         while (i--) push_front(*(begin() + n - 1));
  862.         copy(begin() + n + n, begin() + n + index, begin() + n);
  863.         copy(first, last, begin() + index);
  864.     }
  865.     } else {
  866.     difference_type orig_len = index + remainder;
  867.     if (n > (size_type)remainder) {
  868.         const_iterator m = first + remainder;
  869.         while (m != last) push_back(*m++);
  870.         difference_type i = 0;
  871.         while (i < remainder) push_back(*(begin() + index + i++));
  872.         copy(first, first + remainder, begin() + index);
  873.     } else {
  874.         difference_type i = 0;
  875.         while ((size_type)i < n) push_back(*(begin() + orig_len - n + i++));
  876.         copy_backward(begin() + index, begin() + orig_len - n, 
  877.               begin() + orig_len);
  878.         copy(first, last, begin() + index);
  879.     }
  880.     }
  881. }
  882.  
  883. template <class T , class Alloc>
  884. void deque<T, Alloc>::erase(iterator position) {
  885.     __stl_debug_check(__check_range(position,begin(), end()-1));    
  886.     if (end() - position > position - begin()) {
  887.         copy_backward(begin(), position, position + 1);
  888.         pop_front();
  889.     } else {
  890.         copy(position + 1, end(), position);
  891.         pop_back();
  892.     }
  893. }
  894.     
  895. template <class T , class Alloc>
  896. void deque<T, Alloc>::erase(iterator first, iterator last) {
  897.     __stl_debug_check(__check_range(first,last, start, finish));    
  898.     difference_type n = last - first;
  899.     if (end() - last > first - begin()) {
  900.         copy_backward(begin(), first, last);
  901.         while(n-- > 0) pop_front();
  902.     } else   {
  903.         copy(last, end(), first);
  904.         while(n-- > 0) pop_back();
  905.     }
  906. }
  907.  
  908.  
  909. # undef __iterator__
  910. # undef iterator
  911. # undef const_iterator
  912. # undef size_type
  913.  
  914. // do a cleanup
  915. # undef deque
  916. __END_STL_FULL_NAMESPACE
  917. # define __deque__ __FULL_NAME(deque)
  918.  
  919. # if !defined ( __STL_DEFAULT_TYPE_PARAM)
  920. // provide a "default" deque adaptor
  921. template <class T>
  922. class deque : public __deque__<T,alloc>
  923. {
  924.     typedef deque<T> self;
  925. public:
  926.     typedef __deque__<T,alloc> super;
  927.     __CONTAINER_SUPER_TYPEDEFS
  928.     __IMPORT_SUPER_COPY_ASSIGNMENT(deque)
  929.     deque() : super() { }
  930.     explicit deque(size_type n, const T& value) : super(n, value) { }
  931.     explicit deque(size_type n) : super(n) { }
  932.     deque(const T* first, const T* last) : super(first, last) { }
  933.     deque(const_iterator first, const_iterator last) : super(first, last) { }
  934.     ~deque() { }
  935. };
  936.  
  937. #  if defined (__STL_BASE_MATCH_BUG)
  938. template <class T>
  939. inline bool 
  940. operator==(const deque<T>& x, const deque<T>& y) {
  941.     typedef typename deque<T>::super super;
  942.     return operator == ((const super&)x,(const super&)y);
  943. }
  944.  
  945. template <class T>
  946. inline bool 
  947. operator<(const deque<T>& x, const deque<T>& y) {
  948.     typedef typename deque<T>::super super;
  949.     return operator < ((const super&)x,(const super&)y);
  950. }
  951. #  endif
  952. # endif /* __STL_DEFAULT_TYPE_PARAM */
  953.  
  954. template <class T, class Alloc>
  955. bool operator==(const __deque__<T, Alloc>& x, const __deque__<T, Alloc>& y) {
  956.     return x.size() == y.size() && equal(x.begin(), x.end(), y.begin());
  957. }
  958.  
  959. template <class T, class Alloc>
  960. bool operator<(const __deque__<T, Alloc>& x, const __deque__<T, Alloc>& y) {
  961.     return lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
  962. }
  963.  
  964. # if defined (__STL_CLASS_PARTIAL_SPECIALIZATION )
  965. template <class T, class Alloc>
  966. inline void swap(__deque__<T,Alloc>& a, __deque__<T,Alloc>& b) { a.swap(b); }
  967. # endif
  968.  
  969. __END_STL_NAMESPACE
  970.  
  971. #endif /* __SGI_STL_DEQUE_H */
  972.  
  973.